package main.leetcode.clockin.March;

import main.datastruc.TreeNode;

/**
 * 543.二叉树的直径
 *
 * <p>给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
 *
 * <p>
 *
 * <p>注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day10 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(2);
        root.left.right.left.left = new TreeNode(2);
        root.right.left = new TreeNode(2);
        root.right.left.right = new TreeNode(2);
        System.out.println(new day10().diameterOfBinaryTree(root));
    }

    private int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null || root.left == null && root.right == null) return 0;
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = dfs(root.left); // 左子树最大高度
        int r = dfs(root.right); // 右子树最大高度
        res = Math.max(res, l + r); // 最大直径
        return Math.max(l, r) + 1; // 当前根节点最大直径（返回父节点，父子节点之间的长度为1）
    }
}
